package BinaryTree;

import java.util.Stack;

/*
*二叉搜索树的后续遍历序列
*
* 左右根, 翻过来就是根右左, 相当于另一个方向的前序遍历序列
* 利用单调栈可以判断此序列是否为一个二叉搜索树的逆方向的钱序序列
* */
public class Offer33verifyPostorder {
    public boolean verifyPostorder(int[] postorder) {
        int pre=Integer.MAX_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i=postorder.length-1;i>=0;i--){
            if(postorder[i]>pre){
                return false;
            }
            while (!stack.isEmpty() && postorder[i]<stack.peek()){
                // 全部出栈, 栈底元素赋值给pre,也就是当前节点的父节点, 当前节点就是这个父节点的左子树节点
                pre=stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
